The present invention relates to an adder, a multiplier, and an integrated circuit using either of these, and particularly to an adder, a multiplier and an integrated circuit using this, in which a conventional carry-select system is improved to decrease a circuit quantity and to achieve speed-up.
The recent development of DSP (Digital Signal Processing) is remarkable, and a 32-bit multiplier or the like is used as the central technique. As its structure, a simple multiplier using N2 full adders is not adopted, but a second booth multiplier is usually adopted. This is because since the delay of a carry via an adder is large, the number of partial products (booth muxes) is decreased so as to reduce a circuit quantity and to improve a multiplication speed. With respect to the gathering of the booth muxes, although there is a method of using a CPA (Carry Propagation Adder), in view of the delay of the carry, a Wallace tree is usually adopted.
The Wallace tree is configured by a tree structure of CSAs (Carry Save Adder). Since the CSA performs addition with a separate carry, the propagation of the carry does not occur, and the delay of the carry is also small. However, with respect to the gathered booth muxes, since normal addition is performed by a 65-bit adder at the final stage, the delay of the carry at that portion is a bottleneck in speedup of an adder. Besides, also in a 64-bit multiplier, since a 129-bit high speed adder is required, this is an obstacle to realization of the 64-bit multiplier.
This situation is particularly serious in the field of encryption. In order to increase the secrecy of encryption, it is necessary to perform multi-bit addition, subtraction, multiplication and division, and according to circumstances, residue arithmetic is also needed. Today, it is necessary to handle a number of 1024 bits in the encryption of an RSA system, and a number of 224 bits in an elliptic curve cryptosystem. In order to perform encryption or decryption, and further to attach a signature and to perform its verification, such multi-bit calculation must be performed at high speed.
As methods of raising the speed of an adder, various methods are known. Among them, a carry look-ahead adder, a carry-skip adder, and a carry-select adder are well known. In any of these systems, attention is paid to the fact that the delay of a carry via an adder is large, and an idea of raising its speed is adopted. Among these, the “carry-select adder” has not been conventionally adopted very frequently. This is because in this system, the circuit quantity is increased to raise the cost of an LSI, and it is not suitable for a multi-bit adder.
A conventional 4-bit carry-select adder is constituted by a 4-bit adder with a virtual carry VC0 as an input, a 4-bit adder with a virtual carry VC1 as an input, a first multiplexer for selecting respective addition values S1 and S2 of these two 4-bit adders, and a second multiplexer for selecting respective carry outputs C1 and C2 of these two 4-bit adders.
The structures of the two 4-bit adders are not particularly limited, and the above carry look-ahead adder or the like can be adopted. Although the virtual carry VC0 can be determined to be “0” and the virtual carry VC1 can be determined to be “1”, the contrary may be adopted.
In this conventional carry-select adder, a true carry input Cin is made a selection signal of the first and the second multiplexers, and a true addition value S or carry output Cout is selected. In the two 4-bit adders, since 4-bit inputs P and Q are made common, one of the addition values S1 or S2 always becomes the true addition value S, and one of the corresponding carry outputs C1 or C2 becomes the true carry output Cout.
The conventional carry-select adder of the structure like this has a large merit in calculation speed. When the inputs P and Q are previously determined, in the case where the adders are continuously connected to each other, the calculations are ended substantially at the same time. Thus, thereafter, a true carry has only to be selected, and a calculation time required for addition can be saved. That is, it is unnecessary to consider the propagation of a carry.
However, the conventional carry-select adder requires a circuit quantity two or more times as large as a simple 4-bit adder.
In two full adders used in the conventional carry-select adder, the same input values Pk and Qk are inputted, and the addition value S1 or S2 and the carry Cout1 or Cout2 are respectively outputted. The carry input at the addition is Cin1 or Cin2, and correspondingly to the carry output Cout1 or Cout2, passages of carries independent from each other are formed. Then, one of the addition values S1 or S2 is selected by a multiplexer in accordance with a carry selection signal Cs, and is outputted as an addition value Sk. In the conventional carry-select adder like this, since addition values are selected by the multiplexer after addition of the full adders, the circuit is wasteful.